package com.caochenlei.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //堆排序
    public static void heapSort(int arr[]) {
        //创建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        //调整大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            //交换元素
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //调整新堆
            heapAdjust(arr, 0, i);
        }
    }

    //堆调整
    public static void heapAdjust(int arr[], int index, int length) {
        //缓存当前结点
        int temp = arr[index];
        //开始循环调整
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
            //说明左子结点的值小于右子结点的值
            if (i + 1 < length && arr[i] < arr[i + 1]) {
                i++;
            }
            //说明当前子结点的值大于父结点的值
            if (arr[i] > temp) {
                arr[index] = arr[i];
                index = i;
            } else {
                break;
            }
        }
        //放到调整位置
        arr[index] = temp;
    }
}
